"""
快速排序：
最坏复杂度：O(n^2)
最好复杂度：在 O(n) 和 O(nlogn)中间
"""


def quick_sort(sequence):
    def recursive(begin, end):
        if begin > end:
            return
        left, right = begin, end
        pivot = sequence[left]
        while left < right:
            while left < right and sequence[right] > pivot:
                right = right - 1
            while left < right and sequence[left] <= pivot:
                left = left + 1
            sequence[left], sequence[right] = sequence[right], sequence[left]
        sequence[left], sequence[begin] = pivot, sequence[left]
        recursive(begin, left-1)
        recursive(right+1, end)

    recursive(0, len(sequence)-1)
    return sequence


if __name__ == '__main__':
    sequence = [12, 27, 46, 16, 25, 37, 22, 29, 15, 47, 48, 34]
    print(sequence)
    print(quick_sort(sequence))

